package hot;

public class qijiu {

//    https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked
    //创建一个标记数组
    int m;
    int n;
    char[] word;
    boolean[][] visit;
    public boolean exist(char[][] board, String _word) {
        m=board.length;
        n=board[0].length;
        word=_word.toCharArray();
        visit=new boolean[m][n];
        //先找到word的第一个字符所在的位置
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==word[0]){
                    visit[i][j]=true;
                    //从0开始也行 不过我从1开始 是因为0位置的已经找到了
                    if(dfs(board,i,j,1)){
                        return true;
                    }
                    //记得恢复
                    visit[i][j]=false;
                }
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,int i,int j,int pos){
        if(pos==word.length){
            return true;
        }
        //然后进行上下左右的判断
        //此处采用向量数组来进行处理，一口气搞定上下左右四个方向，不用分别写4个dfs
        int[] dx={0,-1,1,0};
        int[] dy={-1,0,0,1};
        for(int h=0;h<4;h++){
            int x=dx[h]+i;
            int y=dy[h]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&!visit[x][y]&&board[x][y]==word[pos]){
                visit[x][y]=true;
                if(dfs(board,x,y,pos+1)){
                    return true;
                }
                visit[x][y]=false;
            }
        }
        return false;
    }
    }

